import com.kiwi.nixu.common.LNode;
import com.sun.xml.internal.ws.handler.HandlerException;

/**
 * 题目描述：找出单链表中的倒数第k个元素，如给定单链表：1→2→3→4→5→6→7，则单链表的倒数第k=3个元素为5
 */
public class E如何找出链表中的倒数第k个元素 {

    /**
     * 由于单链表只能从头到尾依次访问链表的各个结点，因此如果要找单链表的倒数第k 个元素，
     * 也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，
     * 让其中一个指针比另外一个指针先前移k步，然后两个指针同时往前移动。
     * 循环直到先行的指针值为null时，另一个指针所指的位置就是所要找的位置
     */
    //构造一个单链表
    public static LNode constructList() {
        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        return head;
    }

    public static void printList(LNode head) {
        for (LNode cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
    }

    public static LNode findLastK(LNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        LNode slow, fast;
        slow = fast = head.next;
        int i;
        for (i = 0; i < k && fast != null; ++i) {
            fast = fast.next;
        }
        //判断k是否已超出链表的长度
        if (i < k) {
            return null;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        LNode head = constructList();
        LNode result = null;
        System.out.print("链表：");
        printList(head);
        result = findLastK(head, 3);
        if (result != null) {
            System.out.println("\n 链表倒数第三个元素为：" + result.data);
        }
    }


    /**
     * 引申：如何将单链表向右旋转k个位置。
     * 题目描述：给定单链表1→2→3→4→5→6→7，k=3，那么旋转后的单链表变为5→6→7→1→2→3→4
     */
    private static class 如何将单链表向右旋转k个位置 {

        /**
         * 分析与解答：
         * 主要思路为：
         * ①首先找到链表倒数第k+1个结点slow和尾结点fast（如下图所示）；
         * ②把链表断开为两个子链表，其中后半部分子链表结点的个数为k；
         * ③使原链表的尾结点指向链表的第一个结点；④使链表的头结点指向原链表倒数第k个结点
         */

        public static void rotateK(LNode head, int k) {
            if (head == null || head.next == null) {
                return;
            }
            //fast指针先走k步，然后与slow指针同事向后走
            LNode slow, fast, tmp;
            slow = fast = head.next;
            int i;
            for (i = 0; i < k && fast != null; ++i) {
                fast = fast.next;
            }
            //判断k是否已超出链表长度
            if (i < k) {
                return;
            }
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }

            tmp = slow;
            slow = slow.next;
            tmp.next = null;
            fast.next = head.next;
            head.next = slow;
        }

        public static LNode constructList() {
            int i = 1;
            LNode head = new LNode();
            head.next = null;
            LNode tmp = null;
            LNode cur = head;
            for (; i < 8; i++) {
                tmp = new LNode();
                tmp.data = i;
                tmp.next = null;
                cur.next = tmp;
                cur = tmp;
            }
            return head;
        }

        public static void printList(LNode head) {
            for (LNode cur = head.next; cur != null; cur = cur.next) {
                System.out.print(cur.data + "");
            }
        }

        public static void main(String[] args) {
            LNode head = constructList();
            System.out.println("旋转前");
            printList(head);
            rotateK(head, 3);
            System.out.println("\n旋转后");
            printList(head);
        }
    }
}
